package com.zxy.leetcode._00000_00099._00070_00079;

import java.util.*;

/**
 * https://leetcode-cn.com/problems/combinations/
 *
 * 组合
 * 给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
 *
 * 标签：回溯算法、组合
 */
public class Test00077 {

    public static void main(String[] args) {
        Test00077 test = new Test00077();
        System.out.println(test.combine(4, 2));
    }

    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<>();
        Deque<Integer> selectNums = new ArrayDeque<>();
        backtrack(result, selectNums, n, k);
        return result;
    }

    private void backtrack(List<List<Integer>> result, Deque<Integer> selectNums, int n, int k) {
        if (selectNums.size() == k) {
            result.add(new ArrayList<>(selectNums));
            return;
        }

        int last = 0;
        if (!selectNums.isEmpty()) {
            last = selectNums.getLast();
        }
        for (int i=last + 1; i<=n; i++) {
            selectNums.add(i);
            backtrack(result, selectNums, n, k);
            selectNums.removeLast();
        }
    }
}
